import java.util.Arrays;

public class Test {
    public static void mergeSort(int[] arr) {
        mergeTmp(arr,0,arr.length-1);
    }

    private static void mergeTmp(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = (left+right) >>> 1;

        //分解
        mergeTmp(arr,left,mid);
        mergeTmp(arr,mid+1,right);
        //合并
        merge(arr,left,right,mid);
    }

    private static void merge(int[] arr, int left, int right,int mid) {
        int start1 = left;
        int end1 = mid;
        int start2 = mid+1;
        int end2 = right;
        int[] tmp = new int[right-left+1];
        int index = 0;

        while (start1 <= end1 && start2 <= end2) {
            if (arr[start1] <= arr[start2]) {//一定要<=，这样归并排序才具有稳定性
                tmp[index++] = arr[start1++];
            }else {
                tmp[index++] = arr[start2++];
            }
        }
        while (start1 <= end1) {
            tmp[index++] = arr[start1++];
        }
        while (start2 <= end2) {
            tmp[index++] = arr[start2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            arr[i+left] = tmp[i];
        }
    }



    public static void main(String[] args) {
        int[] arr = {23,122,0,12,5657,12,48,-14,2,7,2,19,24,26,10,88,66,16};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}